#ifndef RADIX_TREE_H
#define RADIX_TREE_H

#include <Types.h>
#include <SlabAllocator.h>
#include <kstdio.h>

extern SlabAllocator *radixTreeNodeAllocator;
#define RTNALLOC	radixTreeNodeAllocator

class RadixTreeNode{
	public:
	void * el[64];
	uint32 count;
	public:
		RadixTreeNode(){
			uint32 i;
			for(i = 0; i < 64; i++){
				el[i] = NULL;
			}
			count = 0;
		}
		inline void ppSize(uint32 sz){
			count += sz;
		}
		inline void mmSize(uint32 sz){
			count -= sz;
		}
		inline uint32 getSize(){
			return count;
		}
		void printNode(){
			uint32 i;
			kprintf("Size:%i\n", count);
			for(i = 0; i < 64; ++i){
				kprintf("(%X) ", el[i]);
			}
		}
};

class RadixTree{
	uint32	height;
	RadixTreeNode *head;
	public:
		RadixTree(){
			height = 0;
			head = NULL;
			radixTreeNodeAllocator = new(privateAllocator) SlabAllocator(sizeof(RadixTreeNode));
		}
	private:
		uint32 growTree(uint32 nr);
		uint32 getHeight(uint32 index);
	public:
		void insertNode(uint32 index, void *elm);
		
		void * getNode(uint32 index);
		
		uint32 removeNode(uint32 index);
		
		void printTree();
};

#endif /*RADIX_TREE_H*/
